A <#204#>pair<#204#> (sometimes called a <#205#>dotted pair<#205#>) is a record structure with two fields called the car and cdr fields (for historical reasons). Pairs are created by the procedure <#206#>cons<#206#>. The car and cdr fields are accessed by the procedures <#207#>car<#207#> and <#208#>cdr<#208#>. The car and cdr fields are assigned by the procedures <#209#>set-car!<#209#> and <#210#>set-cdr!<#210#>.
Pairs are used primarily to represent lists. A list can be defined
recursively as either the empty list
The empty list<#212#>empty list<#212#> is a special object of its own type (it is not a pair); it has no elements and its length is zero.
The most general notation (external representation) for Scheme pairs is the ``dotted'' notation <#1958#>(<#213#>c<#213#> . <#214#>c<#214#>)<#1958#> where <#215#>c<#215#> is the value of the car field and <#216#>c<#216#> is the value of the cdr field. For example <#217#>(4 . 5)<#217#> is a pair whose car is 4 and whose cdr is 5. Note that <#218#>(4 . 5)<#218#> is the external representation of a pair, not an expression that evaluates to a pair.
A more streamlined notation can be used for lists: the elements of the
list are simply enclosed in parentheses and separated by spaces. The
empty list
and
are equivalent notations for a list of symbols.
A chain of pairs not ending in the empty list is called an <#225#>improper list<#225#>. Note that an improper list is not a list. The list and dotted notations can be combined to represent improper lists:
is equivalent to
Whether a given pair is a list depends upon what is stored in the cdr field. When the <#230#>set-cdr!<#230#> procedure is used, an object can be a list one moment and not the next:
It is often convenient to speak of a homogeneous list of objects of some particular data type, as for example <#233#>(1 2 3)<#233#> is a list of integers. To be more precise, suppose <#234#>D<#234#> is some data type. (Any predicate defines a data type consisting of those objects of which the predicate is true.) Then
Within literal expressions and representations of objects read by the
<#244#>read<#244#> procedure, the forms <#245#>datum<#245#><#246#>'<#246#>,
<#247#>datum<#247#>, <#248#>,<#248#><#249#>datum<#249#><#250#>,<#250#>, and
<#251#>,@<#251#><#252#>datum<#252#> denote two-element lists whose first elements are
the symbols <#253#>quote<#253#>, <#254#>quasiquote<#254#>, <#1959#><#255#>unquote<#255#><#1959#>, and
<#256#>unquote-splicing<#256#>, respectively. The second element in each case
is <#257#>datum<#257#>. This convention is supported so that arbitrary Scheme
programs may be represented as lists. <#258#>Can or need this be stated
more carefully?<#258#> That is, according to Scheme's grammar, every
<#259#>expression<#259#> is also a <#260#>datum<#260#> (see section~#datum#261>
0<#1970#>(cadr <#322#>pair<#322#>)<#1970#> 1<#323#>essential procedure<#323#>